package dp.多少种方案;

/**
 * https://leetcode-cn.com/problems/unique-paths/
 *
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 不同路径62.java
 * @createTime 2021年12月27日 20:31:00
 *
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 *
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 *
 * 问总共有多少条不同的路径？
 *
 */
public class 不同路径62 {
	public int uniquePaths(int m, int n) {
		//定义dp[i][j]表示 位置i,j的方案数量
		int[][] dp=new int[m][n];

		/*
		 * 初始化状态
		 *   当i=0的时候，所有的位置j的方案数量为1
		 *   当j=0的时候，所有位置i的方案数量为1
		 */
		for (int i = 0; i < m; i++) {
			dp[i][0]=1;
		}
		for (int j = 0; j < n; j++) {
			dp[0][j]=1;
		}

		/*
		 * 状态转移方程，
		 *  dp[i][j]=dp[i-1][j]+dp[i][j-1]
		 */
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				dp[i][j]=dp[i-1][j]+dp[i][j-1];
			}
		}
		return dp[m-1][n-1];
	}
}
